class Solution:
    def tribonacci(self, n: int) -> int:
        f = [0, 1, 1] + [0] * (n - 2)
        for i in range(3, n + 1):
            f[i] = f[i - 1] + f[i - 2] + f[i - 3]
        return f[n]


class Solution:
    def tribonacci(self, n: int) -> int:
        base = [[1, 1, 0]]
        if n < 3:
            return base[0][(2 - n)]
        mul = [[1, 1, 0], [1, 0, 1], [1, 0, 0]]

        def multiply(a, b):
            m, n, p = len(a), len(a[0]), len(b[0])
            ans = [[0] * p for _ in range(m)]
            for i in range(m):
                for j in range(p):
                    for k in range(n):
                        ans[i][j] += a[i][k] * b[k][j]
            return ans

        def pow_array(p, q):
            n = len(p)
            ans = [[0] * n for _ in range(n)]
            for i in range(n):
                ans[i][i] = 1
            while q > 0:
                if q & 1 == 1:
                    ans = multiply(ans, p)
                p = multiply(p, p)
                q >>= 1

            return ans

        return multiply(base, pow_array(mul, n - 2))[0][0]


so = Solution()
print(so.tribonacci(1))
